#define getbit(x, i) (x&(0x00000001<<i))?1:0
class Solution {
public:
    int integerReplacement(int n)
    {
        if(n == INT32_MAX) {
            return 32;
        }
        int r = 0;
        while(n != 1) {
            if(!getbit(n, 0)) {
                n >>= 1;
            } else if(n != 3 && getbit(n, 1)) {
                n += 1;
            } else {
                n -= 1;
            }
            r++;
        }
        return r;
    }
};